package com.lx.algorithm.recursion.class18;

import com.lx.algorithm.Utils;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-18 12:32:03
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-18     张李鑫                     1.0         1.0 Version
 */
public class CardsInLine {
    /**
     * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
     * 玩家A和玩家B依次拿走每张纸牌
     * 规定玩家A先拿，玩家B后拿
     * 但是每个玩家每次只能拿走最左或最右的纸牌
     * 玩家A和玩家B都绝顶聪明
     * 请返回最后获胜者的分数。
     */

    public static int win(int[] arr) {
        return Math.max(pre(arr, 0, arr.length - 1), after(arr, 0, arr.length - 1));
    }


    /**
     * 先手拿牌
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int pre(int[] arr, int l, int r) {
        //如果相等 就拿这张
        if (l == r) {
            return arr[l];
        }
        //以下个区间拿牌 获取最大值
        int left = after(arr, l + 1, r) + arr[l];
        int right = after(arr, l, r - 1) + arr[r];
        return Math.max(left, right);
    }

    /**
     * 后手视角
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int after(int[] arr, int l, int r) {
        //如果只有一张牌了 后手就不能在拿了
        if (l == r) {
            return 0;
        }
        //以下个区间先手去拿牌 获取最小值
        int left = pre(arr, l + 1, r);
        int right = pre(arr, l, r - 1);
        return Math.min(left, right);
    }

    public static int dp(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] pre = new int[arr.length][arr.length];
        int[][] after = new int[arr.length][arr.length];

        //先填pre对角线的数据
        for (int i = 0; i < pre.length; i++) {
            pre[i][i] = arr[i];
        }
        for (int i = arr.length - 2; i >= 0; i--) {
            int l = i;
            int r = arr.length - 1;
            //从倒数第二个行开始填写斜线来
            while (l >= 0) {
                after[l][r] = Math.min(pre[l + 1][r], pre[l][r - 1]);
                pre[l][r] = Math.max(arr[l] + after[l + 1][r], arr[r] + after[l][r - 1]);
                l--;
                r--;
            }
        }
        return Math.max(pre[0][arr.length - 1], after[0][arr.length - 1]);
    }

    /**
     * 老师代码
     *
     * @param arr
     * @return
     */
    public static int win3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
        }
        for (int startCol = 1; startCol < N; startCol++) {
            int L = 0;
            int R = startCol;
            while (R < N) {
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }


    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            int[] arr = Utils.generateRandomMatrix(20);
            int dp = dp(arr);
            int dp2 = win3(arr);
            if (dp != dp2) {
                System.out.println("error");
                break;
            }
        }

    }

}
